

int coinChange(int* coins, int coinsSize, int amount){
    if (amount == 0) return 0;
    // dp[i] 表示填满容量为i的背包，最少需要的硬币个数
    int *dp = malloc(sizeof(int) * (amount+1));
    dp[0] = 0;
    for (int j = 1; j <= amount; j++) dp[j] = INT_MAX;

    for (int i = 1; i <= amount; i++) {
        for (int j = 0; j < coinsSize; j++) {
            //转移方程：dp[j] = min(dp[j], dp[j - coin] + 1)
            //当前填满容量j最少需要的硬币 = min( 之前填满容量j最少需要的硬币, 填满容量 j - coin 需要的硬币 + 1个当前硬币）

            // dp[i - conis[j]] == INT_MAX表示凑不出硬币的情况
            if (i - coins[j] >= 0 && dp[i - coins[j]] != INT_MAX)
                dp[i] = fmin(dp[i], dp[i - coins[j]]+1);
        }
    }
    return (dp[amount] == INT_MAX)? -1:dp[amount];
}



